import java.util.*;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 中等
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

 * 思路
 * 1.哈希表记录数字对应的字符集
 * 2.深搜所有组合情况
 * @since 2023-08-27 17:27
 */
public class _017电话号码的字母组合 {
    private static List<String> res;
    private static StringBuilder builder;
    static Map<Integer, List<String>> map;
    public static List<String> letterCombinations(String digits) {
        //哈希表记录数字对应的字符集
        map = new HashMap<>();
        map.put(2, Arrays.asList("a", "b", "c"));
        map.put(3, Arrays.asList("d", "e", "f"));
        map.put(4, Arrays.asList("g", "h", "i"));
        map.put(5, Arrays.asList("j", "k", "l"));
        map.put(6, Arrays.asList("m", "n", "o"));
        map.put(7, Arrays.asList("p", "q", "r", "s"));
        map.put(8, Arrays.asList("t", "u", "v"));
        map.put(9, Arrays.asList("w", "x", "y", "z"));
        res = new ArrayList<>();
        if(digits.length() <= 0) return res;
        builder = new StringBuilder();
        dfs(digits, 0);
        return res;
    }
    //深搜所有组合情况
    private static void dfs(String digits, int index){
        if(index >= digits.length()){
            res.add(builder.toString());
            return;
        }
        int num = Integer.parseInt(digits.charAt(index) + "");
        for(String c : map.get(num)){
            builder.append(c);
            dfs(digits, index + 1);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
    public static void main(String[] args) {
        List<String> res = letterCombinations("23");
        System.out.println(res);
    }
}
